package afi;

public class SquareRoot {

	public int sqrt(int v){
		return _sqrt(v,1,v);
	}
	
	public int _sqrt(int v, int l, int h){
		if(h-l < 2)
			return l;
		int m = (l+h)/2;
		int m2 = m*m;
		
		if(m2 == v)
			return m;
		if(m2 > v)
			return _sqrt(v,l,m);
		else
			return _sqrt(v,m,h);
	}
	
	
	
	public int sqrt2(int v){
		int l=1, h=v, m, m2;
		while(h-l > 1){
			m = l + (h-l)/2;
			m2 = m*m;
			if(m2 == v)
				return m;
			if(m2 < v)
				l=m;
			else
				h=m;
		}
		return l;
	}
	
	public static void main(String[] args) {
		SquareRoot sr = new SquareRoot();
		for (int i = 1; i < 100; i++) {
			System.out.println(sr.sqrt2(i) == Math.floor(Math.sqrt(i)));
		}
		
	}
}
